package Algorithm.dynamicProgramming;

/**
 * 375. 猜数字大小 II https://leetcode.cn/problems/guess-number-higher-or-lower-ii/
 * todo 其它解法
 */
public class GetMoneyAmount {

    public static void main(String[] args) {
        new GetMoneyAmount().getMoneyAmount(10);
    }

    /**
     * 动态规划 —— 记忆化搜索
     * 定义dp：dp[i][j]为从[i, j]搜索数字最坏情况最小花费
     * 状态转移公式：i=j时dp[i][j]=0；i=j-1时dp[i][j]=i；否则dp[i][j] = min(k + max(dp[i][k-1], dp[k+1][j]))
     * 记忆化搜索：由于计算dp[i][j]时会重复用到之前计算过的结果，故用一个dp[][]数组存储已计算结果，
     *          要用时直接取用无需再重复计算。
     */
    int[][] dp;
    public int getMoneyAmount(int n) {
        dp = new int[n+1][n+1];
        return getDP(1, n);
    }
    public int getDP(int i, int j) {
        //i=j时dp[i][j]=0；i=j-1时dp[i][j]=i；
        if (i == j) return 0;
        if (i == j-1) return i;
        //若dp[i][j]已计算过则直接返回
        if (dp[i][j] != 0) return dp[i][j];

        int min = Integer.MAX_VALUE;
        for (int k = i+1;k < j;k++) {
            min = Math.min(min, k + Math.max(getDP(i, k-1), getDP(k+1, j)));
        }
        dp[i][j] = min;
        return min;
    }

}
